#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<string.h>

struct TreeNode {
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
};

struct TreeNode* CRE(int x)
{
	struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
	node->val = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}
bool _isSymmetric(struct TreeNode* p, struct TreeNode* q)
{
	if (p == NULL && q == NULL)
		return true;
	if (p == NULL || q == NULL)
		return false;
	if (p->val != q->val)
		return false;
	return _isSymmetric(p->left, q->right) && _isSymmetric(p->right, q->left);
}

bool isSymmetric(struct TreeNode* root)
{

	return _isSymmetric(root->left, root->right);
}
struct TreeNode* creat()
{
	struct TreeNode* node1 = CRE(1);
	struct TreeNode* node2 = CRE(2);
	struct TreeNode* node3 = CRE(2);
	struct TreeNode* node4 = CRE(3);
	struct TreeNode* node5 = CRE(4);
	struct TreeNode* node6 = CRE(4);
	struct TreeNode* node7 = CRE(3);

	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	node3->left = node6;
	node3->right = node7;

	return node1;
}
int main()
{

	struct TreeNode* root = creat();
	isSymmetric(root);
	return 0;
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 /**
  * Note: The returned array must be malloced, assume caller calls free().
  */
//int treesize(struct TreeNode* root)
//{
//	return root == NULL ? 0 : treesize(root->left) + treesize(root->right) + 1;
//}
//void preOrder(struct TreeNode* root, int* a, int* pi)
//{
//	if (root == NULL)
//		return;
//	a[(*pi)++] = root->val;
//	preOrder(root->left, a, pi);
//	preOrder(root->right, a, pi);
//}
//int* preorderTraversal(struct TreeNode* root, int* returnSize) {
//	*returnSize = treesize(root);
//	int* a = (int*)malloc(sizeof(int) * (*returnSize));
//	int n = 0;
//	preOrder(root, a, &n);
//
//	return a;
//}
